Transitieve afsluiting

De transitieve afsluiting (Nederland) of transitieve sluiting (Vlaanderen) ${\displaystyle R^{+}}$ van een tweeplaatsige relatie ${\displaystyle R}$ op een verzameling ${\displaystyle M}$ is de kleinste transitieve relatie op ${\displaystyle M}$ die de oorspronkelijke relatie omvat. Deze kleinste relatie ${\displaystyle R^{+}}$ bestaat altijd, deze kan namelijk als volgt worden geconstrueerd:

${\displaystyle xR^{+}y}$ als er een rij elementen ${\displaystyle x_{0}=x,\,x_{1},\,\ldots ,\,x_{n}=y}$ bestaat met ${\displaystyle n\geq 1}$ en ${\displaystyle x_{i}Rx_{i+1}}$ voor ${\displaystyle 0\leq i<n}$

Deze vorm van afsluiting, gedefinieerd voor tweeplaatsige relaties, komt overeen met de definitie van afsluiting, gedefinieerd voor verzamelingen.

Als men de relaties voorstelt als een gerichte graaf, bevat de graaf van de transitieve afsluiting ${\displaystyle R^{+}}$ een boog van knoop ${\displaystyle x}$ naar knoop ${\displaystyle y}$ als de graaf van ${\displaystyle R}$ een gericht pad met een of meer bogen bevat van ${\displaystyle x}$ naar ${\displaystyle y}$. De transitieve afsluiting van een gerichte, acyclische graaf is de graaf, die aangeeft welke knooppunten vanuit andere knopen zijn te bereiken.

De reflexief-transitieve afsluiting van iedere homogene tweeplaatsige relatie is een preorde.